/*
 *  Copyright (C) 2010 Matthias Buch-Kromann <mbk.isv@cbs.dk>
 * 
 *  This file is part of the IncrementalParser package.
 *  
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package org.osdtsystem.incparser.graphs;

import java.util.Arrays;

/**
 * A local graph with an arbitrary number of in- and out-edges.
 * Nodes, edge types, and edges are represented as integers.
 * An edge consists of a bit sequence of length Graph.NODEBITS
 * which encodes the node, followed by a bit sequence of length Graph.TYPEBITS which
 * encodes the type. 
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class LocalGraphIntArray extends AbstractLocalGraph {
    // Local variables
    short inDegree, outDegree;
    int[] edges;

    public LocalGraphIntArray(int inDegree, int outDegree, int[] edges) {
        this.inDegree = (short) inDegree;
        this.outDegree = (short) outDegree;
        this.edges = edges;
    }

    public int degree() {
        return inDegree() + outDegree();
    }

    public int inDegree() {
        return inDegree;
    }

    public int outDegree() {
        return outDegree;
    }

    public int type(int edge) {
        return Helper.otherPart(edge);
    }

    public int node(int edge) {
        return Helper.nodePart(edge);
    }

    public int edge(int node, int type) {
        return Helper.pack(node, type);
    }

    public int inEdge(int index) {
        return edges[index];
    }

    public int inEdgeNode(int index) {
        return node(inEdge(index));
    }

    public int inEdgeType(int index) {
        return type(inEdge(index));
    }

    public int headEdge() {
        return inDegree > 0 ? inEdge(0) : 0;
    }

    public int headNode() {
        return inDegree > 0 ? inEdgeNode(0) : 0;
    }

    public int headType() {
        return inDegree > 0 ? inEdgeType(0) : 0;
    }

    public int outEdgeNode(int index) {
        return node(outEdge(index));
    }

    public int outEdgeType(int index) {
        return type(outEdge(index));
    }


    public int outEdge(int index) {
        return edges[inDegree() + index];
    }

    public int[] outFrame() {
        return outFrame(Integer.MAX_VALUE);
    }

    public int[] outFrame(int typeMax) {
        // Count number of out-edges whose type is at most typeMax
        int count = 0;
        for (int i = outDegree() - 1; i >= 0; --i) {
            if (type(outEdge(i)) <= typeMax)
                ++count;
        }

        // Store edges in array
        int[] outFrame = new int[count];
        for (int i = outDegree() - 1; i >= 0; --i) {
            int outEdge = outEdge(i);
            if (type(outEdge) <= typeMax) {
                outFrame[--count] = outEdge;
            }
        }

        // Return array
        return outFrame;
    }

    public void addInEdge(int edge) {
        // Ensure edge capacity
        ++inDegree;
        ensureEdgeCapacity();

        // Shift out-edges to the right, and insert new in-edge
        for (int i = degree() - 1; i >= inDegree(); --i) {
           edges[i] = edges[i-1];
        }
        edges[inDegree() - 1] = edge;
        sortInEdges();
    }


    public void addOutEdge(int edge) {
        ++outDegree;
        ensureEdgeCapacity();
        edges[degree() - 1] = edge;
        sortOutEdges();
    }

    public int inEdgeIndex(int edge) {
        for (int i = inDegree() - 1; i >= 0; --i) {
            if (edges[i] == edge)
                return i;
        }
        return -1;
    }

    public int outEdgeIndex(int edge) {
        for (int i = inDegree(); i < edges.length; ++i) {
            if (edges[i] == edge)
                return i;
        }
        return -1;
    }

    void removeInEdge(int edge) {
        int index = inEdgeIndex(edge);
        if (index < 0 || index >= inDegree())
            return;
        --inDegree;
        for (int i = index; i < degree(); ++i) {
            edges[i] = edges[i+1];
        }
    }

    void removeOutEdge(int edge) {
        int index = outEdgeIndex(edge);
        if (index < 0 || index >= outDegree())
            return;
        --outDegree;
        for (int i = index; i < degree(); ++i) {
            edges[i] = edges[i+1];
        }
    }

    void clear() {
        outDegree = 0;
        inDegree = 0;
    }

    public void trimToSize() {
        if (edges.length != degree()) {
            edges = Arrays.copyOf(edges, degree());
        }
    }

    @Override
    public LocalGraphIntArray clone() {
        LocalGraphIntArray clone = (LocalGraphIntArray) super.clone();
        clone.edges = edges.clone();
        return clone;
    }

    void ensureEdgeCapacity() {
        if (degree() > edges.length) {
            edges = Arrays.copyOf(edges, degree());
        }
    }

    void sortInEdges() {
        Arrays.sort(edges, 0, inDegree());
    }

    void sortOutEdges() {
        Arrays.sort(edges, inDegree(), degree());
    }
}
